import java.util.Arrays;

// https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
// 1005. K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] <= 0) {
                nums[i] = -nums[i];
                k--;
            } else if (k > 0) {
                Arrays.sort(nums);
                if (k % 2 == 1) {
                    nums[0] = -nums[0];
                    k = 0;
                }
                break;
            }
        }
        if (k > 0 && k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }

        return Arrays.stream(nums).sum();
    }
}